
/**
 * Created by IntelliJ
 * Author:熊磊
 */
public class KrusKal {
    private int edgeNum;
    private char[] vertexs;
    private int[][] matrix;

    private static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        char[] vertexs = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] matrix=new int[][]{
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };
        KrusKal krusKal = new KrusKal(vertexs,matrix);
        krusKal.kruskal();
    }

    public KrusKal(char[] vertexs,int[][] matrix){
        this.vertexs=vertexs;
        this.matrix=matrix;
        for (int[] x : matrix) {
            for (int item : x) {
                if (item!=INF&&item>0){
                    edgeNum++;
                }
            }
        }
        edgeNum /=2;
    }

    public void print(){
        System.out.println("A B C D E F G");
        for (int[] x : matrix) {
            for (int item : x) {
                if (item==INF){
                    System.out.printf("m\t");
                }else {
                    System.out.printf("%d\t", item);
                }
            }
            System.out.println();
        }
    }

    public void sortEdges(EData[] edges){
        for (int i = 0; i < edges.length-1; i++) {
            for (int j = 0; j < edges.length-1-i; j++) {
                if (edges[j].weight>edges[j+1].weight){
                    EData temp = edges[j];
                    edges[j]=edges[j+1];
                    edges[j+1] = temp;
                }
            }
        }
    }

    public int getPosition(char ch){
        for (int i = 0; i < vertexs.length; i++) {
            if (vertexs[i]==(ch)){
                return i;
            }
        }
        return -1;
    }

    public EData[] getEdges(){
        int index = 0 ;
        EData[] edges = new EData[edgeNum];
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = i+1; j < vertexs.length; j++) {
                if (matrix[i][j]!=INF){
                    edges[index++] =new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }

        return edges;
    }

    public int getEnd(int[] ends,int i){
        while (ends[i]!=0){
            i = ends[i];
        }
        return i;
    }

    public void kruskal(){
        int index =0;
        int[] ends = new int[edgeNum];
        EData[] rets = new EData[vertexs.length-1];

        EData[] edges = getEdges();
        sortEdges(edges);
        for (int i = 0; i < edges.length; i++) {
            int p1 = getPosition(edges[i].start);
            int p2 = getPosition(edges[i].end);
            int m = getEnd(ends, p1);
            int n = getEnd(ends, p2);
            if (m!=n){
                ends[m] =n;
                rets[index++]=edges[i];
            }
        }

        //print
        for (EData ret : rets) {
            System.out.println(ret);
        }
    }
}

class EData {
    char start;
    char end;
    int weight;

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}